package com.swjd.tree;

/**
 * 二叉树
 *
 * @author 刘涛
 * @create 2021/9/30 23:09
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一个二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");

        //暂时手动生成二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);

        //测试
        System.out.println("前序遍历");
        binaryTree.preorder();
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.afterOrder();

        //前序查找
        System.out.println("前序查找~~");
        System.out.println(binaryTree.preorderFind(5));
        System.out.println("中序查找~~");
        System.out.println(binaryTree.infixOrderFind(5));
        System.out.println("后序查找~~");
        System.out.println(binaryTree.afterOrderFind(5));

        //删除节点
        System.out.println("删除前：");
        binaryTree.preorder();
        System.out.println("删除后：");
        binaryTree.delNode(5);
        binaryTree.preorder();
    }
}

/**
 * 二叉树
 */
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    /**
     * 前序遍历
     */
    public void preorder() {
        if (this.root != null) {
            this.root.preorder();
        } else {
            System.out.println("二叉树空！无法遍历");
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树空！无法遍历");
        }
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.root != null) {
            this.root.afterOrder();
        } else {
            System.out.println("二叉树空！无法遍历");
        }
    }

    /**
     * 前序遍历查找
     *
     * @param no 要查找的英雄编号
     * @return 查找到的节点
     */
    public HeroNode preorderFind(int no) {
        if (this.root != null) {
            return root.preorderFind(no);
        } else {
            return null;
        }
    }

    /**
     * 中序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode infixOrderFind(int no) {
        if (this.root != null) {
            return root.infixOrderFind(no);
        } else {
            return null;
        }
    }

    /**
     * 后序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode afterOrderFind(int no) {
        if (this.root != null) {
            return root.afterOrderFind(no);
        } else {
            return null;
        }
    }

    /**
     * 删除节点
     *
     * @param no 需要删除节点的编号
     */
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("空树，无法删除！");
        }
    }
}

/**
 * 英雄树节点
 */
class HeroNode {
    private int no;//编号
    private String name;//名字
    private HeroNode left;//左子节点
    private HeroNode right;//右子节点

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    /**
     * 前序遍历
     */
    public void preorder() {
        System.out.println(this);//先输出父节点
        //递归左子树
        if (this.left != null) {
            this.left.preorder();
        }
        //递归向右子树
        if (this.right != null) {
            this.right.preorder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);//打印父节点
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.left != null) {
            this.left.afterOrder();
        }
        if (this.right != null) {
            this.right.afterOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找
     *
     * @param no 要查找的英雄编号
     * @return 查找到的节点
     */
    public HeroNode preorderFind(int no) {
        HeroNode resNode = null;
        if (this.no == no) {//如果编号相同 就返回
            return this;
        }
        if (this.left != null) {
            resNode = this.left.preorderFind(no);//继续向左遍历查找 如果查找到了就会给resNode值
        }
        if (resNode != null) {
            //不为空就代表找到了
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preorderFind(no);//继续向右遍历查找 如果查找到了就会给resNode值
        }
        return resNode;//由于上面的左右都以及全部遍历完成了，所以这里无论是否找到都需要返回结果了
    }

    /**
     * 中序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode infixOrderFind(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderFind(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderFind(no);
        }
        return resNode;
    }

    /**
     * 后序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode afterOrderFind(int no) {
        HeroNode resNode = null;
        if (this.left != null) { //如果左节点不为空，继续递归
            resNode = this.left.afterOrderFind(no);
        }
        if (resNode != null) {//如果resNode有值了，就代表上面的递归找打了
            return resNode;
        }
        if (this.right != null) {//如果右节点不为空，就继续递归
            resNode = this.right.afterOrderFind(no);
        }
        if (resNode != null) {//如果resNode有值了，就说明上面的递归找到了
            return resNode;
        }
        if (this.no == no) {//如果左边右边都没找到，就判断当前的
            return this;
        }
        return null;//左节点没找到，右节点没找到，当前节点没找到,就可以返回空了
    }

    /**
     * 删除节点
     *
     * @param no 需要删除的节点编号
     */
    public void delNode(int no) {
        //首先判断左子节点不为空，如果为空直接判断no的话容易报空指针异常
        if (this.left != null && this.left.no == no) {
            //如果要删除的子节点右边不为空
            if (this.left.right != null) {
                //就将节点的左边挂到节点的右边的左边上，再将右节点替换掉删除的节点
                this.left.right.left = this.left.left;
                this.left = this.left.right;
                return;
            }
            //如果左节点不为空，右节点为空，就直接将左节点替换该节点
            if (this.left.left != null) {
                this.left = this.left.left;
                return;
            }
            //左右都为空就代表该节点为叶子节点，就直接置为空
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            //如果要删除的子节点右边不为空
            if (this.right.right != null) {
                //就将节点的左边挂到节点的右边的左边上，再将右节点替换掉删除的节点
                this.right.right.left = this.right.left;
                this.right = this.right.right;
                return;
            }
            //如果左节点不为空，右节点为空，就直接将左节点替换该节点
            if (this.right.left != null) {
                this.right = this.right.left;
                return;
            }
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

}